//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
//子数组是数组中元素的连续非空序列。

//示例 1：
//输入：nums = [1,1,1], k = 2
//输出：2
//示例 2：
//输入：nums = [1,2,3], k = 3
//输出：2

//提示：
//1 <= nums.length <= 2 * 104
//-1000 <= nums[i] <= 1000
//-107 <= k <= 107

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans =0;
        int len = nums.size();

        // build a hash table of sum:indexes
        unordered_map<int, vector<int>> hash_sum; //sum- indexes
        int sum = nums[0];
        vector<int> sum_vec={sum};
        hash_sum[sum].emplace_back(0);
        for(int i=1; i<len; ++i){
            sum += nums[i];
            sum_vec.emplace_back(sum);
            hash_sum[sum].emplace_back(i);
        }

        for(int i=0; i<len; ++i){
            auto iter= hash_sum.find(k + sum_vec[i]);
            if (iter != hash_sum.end()){
                //sum(0,j)- sum(0,i) = k   j>i
               for(auto j: iter->second){
                   if (j>i) ++ans;
               }
            }
        }

        //sum的头应该是什么都不装，为0
        auto iter = hash_sum.find(k);
        if(iter !=hash_sum.end())
            ans += iter->second.size();
        return ans;
    }
};

int main() {
    vector<int> nums0 = {1,1,1}; int k0=2;
    vector<int> nums1 = {1,2,3}; int k1=3;
    vector<int> nums2 = {1}; int k2=0;
    auto &num = nums2 ; int k = k2;

    Solution solution;
    int ans = solution.subarraySum(num, k);
    cout<< ans<<endl;

    return 0;
}
